﻿package szys;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

class Rational {
	private long m_up;
	private long m_down;

	public Rational() {

	}

	public Rational(long up, long down) {
		super();
		// 约分
		long g = gcd(up >= 0 ? up : -up, down > 0 ? down : -down);
		this.m_up = up / g;
		this.m_down = down / g;
	}

	public long getM_up() {
		return m_up;
	}
	
	public long getM_down() {
		return m_down;
	}

	private static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	public Rational add(Rational r) {
		long up = m_up * r.m_down + m_down * r.m_up;
		long down = m_down * r.m_down;
		return new Rational(up, down);
	}

	public Rational subtract(Rational r) {
		long up = m_up * r.m_down - m_down * r.m_up;
		long down = m_down * r.m_down;
		return new Rational(up, down);
	}

	public Rational multiply(Rational r) {
		long up = m_up * r.m_up;
		long down = m_down * r.m_down;
		return new Rational(up, down);
	}

	//不会有除0错误，哇哈哈哈！！！
	public Rational divide(Rational r) {
		long up = m_up * r.m_down;
		long down = m_down * r.m_up;
		return new Rational(up, down);
	}

	private static long quickPow(long a, int n) {
		long res = 1;
		while (n > 0) {
			if ((n & 1) == 1) {
				res *= a;
			}
			a *= a;
			n >>= 1;
		}
		return res;
	}

	public Rational pow(int n) {
		return new Rational(quickPow(m_up, n), quickPow(m_down, n));
	}

	@Override
	public String toString() {
		if (m_down < 0) {
			m_up = -m_up;
			m_down = -m_down;
		}
		return m_up + (m_down == 1 ? "" : "/" + m_down);
	}
}

class Node {
	private String val;
	private Node left, right;

	public Node() {
		val = null;
		left = right = null;
	}

	public Node(String val, Node left, Node right) {
		super();
		this.val = val;
		this.left = left;
		this.right = right;
	}

	public String getVal() {
		return val;
	}

	public Node getLeft() {
		return left;
	}

	public Node getRight() {
		return right;
	}

}


//比较两个最小表示法字符串的大小
class MinPreFormatComparator implements Comparator<MinPreFormat> {

	@Override
	public int compare(MinPreFormat o1, MinPreFormat o2) {
		ArrayList<String> list1 = o1.getVal();
		ArrayList<String> list2 = o2.getVal();
		int lim = Math.min(list1.size(), list2.size());
		for (int i = 0; i < lim; i++) {
			if (!list1.get(i).equals(list2.get(i))) {
				return list1.get(i).compareTo(list2.get(i));
			}
		}
		return list1.size() - list2.size();
	}
}

class MinPreFormat {
	private ArrayList<String> val;
	
	public MinPreFormat() {
		
	}

	public MinPreFormat(ArrayList<String> val) {
		this.val = val;
	}

	public ArrayList<String> getVal() {
		return val;
	}


	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((val == null) ? 0 : val.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		MinPreFormat other = (MinPreFormat) obj;
		if (val == null) {
			if (other.val != null)
				return false;
		} else if (!val.equals(other.val))
			return false;
		return true;
	}

}


class ExpAndAns {
	String exp;
	Rational ans;
	public String getExp() {
		return exp;
	}
	public Rational getAns() {
		return ans;
	}
	
	public ExpAndAns() {
		
	}
	
	public ExpAndAns(String exp, Rational ans) {
		super();
		this.exp = exp;
		this.ans = ans;
	}
	
}






public class Arithmetic {
	
	private static int count(char c) {
		if (c == '=')
			return 0;
		if (c == '(')
			return 1;
		if (c == '+')
			return 2;
		if (c == '-')
			return 3;
		if (c == '*')
			return 4;
		if (c == '/')
			return 5;
		if (c == '^')
			return 6;
		return 7;
	}

	
	private static boolean isNum(String exp, int pos) {
		char ch = exp.charAt(pos);
		if (ch >= '0' && ch <= '9') {
			return true;
		}
		return false;
	}

	
	private static String trans(String exp) {

		// 负数都用括号括起来
		for (int i = 0; i < exp.length(); i++) {
			if (exp.charAt(i) == '-' && exp.charAt(i - 1) == '(') {
				exp = exp.substring(0, i) + '0' + exp.substring(i, exp.length());
				i++;
			}
		}
		// System.out.println(exp);

		String postexp = new String();
		int lpri[] = { 0, 1, 3, 3, 5, 5, 7, 8 }; // =(+-*/^)
		int rpri[] = { 0, 8, 2, 2, 4, 4, 6, 1 };

		ArrayList<Character> op = new ArrayList<>();

		op.add('=');
		for (int i = 0; i < exp.length();) {
			if (isNum(exp, i)) {
				while (i < exp.length() && isNum(exp, i)) {
					postexp += exp.charAt(i);
					i++;
				}
				postexp += '#';
			} else {
				if (lpri[count(op.get(op.size() - 1))] < rpri[count(exp.charAt(i))]) {
					op.add(exp.charAt(i));
					i++;
				} else if (lpri[count(op.get(op.size() - 1))] == rpri[count(exp.charAt(i))]) {
					op.remove(op.size() - 1);
					i++;
				} else {
					postexp += op.get(op.size() - 1);
					op.remove(op.size() - 1);
				}
			}
			// for (Character character : op) {
			// System.out.print(character + " ");
			// }
			// System.out.println();
		}

		while (!op.isEmpty() && op.get(op.size() - 1) != '=') {
			postexp += op.get(op.size() - 1);
			op.remove(op.size() - 1);
		}

		return postexp;
	}
	
	
	// 操作数不超过5个，操作符不超过4个，括号不超过3对，乘方只能有一个，而且次数只能小于等于3
	private static final int MAX_NUMS = 5;
	private static final int MIN_NUMS = 2;
	private static final int MAX_PAIRS = 2;

	
	private static String generateNewExp() {
		// 产生基本的算式

		String exp = new String();
		Random random = new Random();
		int nums = random.nextInt(MAX_NUMS - MIN_NUMS + 1) + MIN_NUMS;
		int pairs = random.nextInt(MAX_PAIRS + 1);
		HashMap<Integer, Integer> leftPosMap = new HashMap<>();
		HashMap<Integer, Integer> rightPosMap = new HashMap<>();
		for (int i = 0; i < nums; i++) {
			leftPosMap.put(i + 1, 0);
			rightPosMap.put(i + 1, 0);
		}
		for (int i = 0; i < pairs; i++) {
			int leftPos = random.nextInt(nums) + 1;
			int rightPos = random.nextInt(nums - leftPos + 1) + leftPos;
//			System.out.println(leftPos + " " + rightPos);
			leftPosMap.put(leftPos, leftPosMap.get(leftPos) + 1);
			rightPosMap.put(rightPos, rightPosMap.get(rightPos) + 1);
		}
		boolean hasPow = false;

		for (int i = 0; i < nums; i++) {

			boolean needContinue = false;
			
			if (i != 0) {
				int op = random.nextInt(5);
				switch (op) {
				case 0:
					exp += "+";
					break;
				case 1:
					exp += "-";
					break;
				case 2:
					exp += "*";
					break;
				case 3:
					exp += "/";
					break;
				default:
					if (hasPow) {
						needContinue = true;
						i--;
					} else {
						exp += "^";
						hasPow = true;
					}
					break;
				}
				
				if (needContinue) {
					continue;
				}

			}
			
			int leftNums = leftPosMap.get(i + 1);

			for (int j = 0; j < leftNums; j++) {
				exp += "(";
			}
			
			if (exp.length() > leftNums && exp.charAt(exp.length() - leftNums - 1) == '^') {
				int matchPos = i + 1;
				for (int j = 0; j < leftNums; j++) {
					exp = exp.substring(0, exp.length() - 1);
					while (rightPosMap.get(matchPos) <= 0) {
						matchPos++;
					}
					rightPosMap.put(matchPos, rightPosMap.get(matchPos) - 1);
				}
				exp += random.nextInt(4);
			} else {
				int generateNum = (random.nextInt(40) - 20);
				if (generateNum < 0 && (leftPosMap.get(i + 1) == 0 || rightPosMap.get(i + 1) == 0)) {
					exp += "(" + generateNum;
					rightPosMap.put(i + 1, rightPosMap.get(i + 1) + 1);
				} else {
					exp += generateNum;
				}
			}
			int rightNums = rightPosMap.get(i + 1);
			for (int j = 0; j < rightNums; j++) {
				exp += ")";
			}
//			System.out.println(exp);
		}
		return exp;
		// 加括号
	}
	
	private static Rational calc(String postexp) {
		ArrayList<Rational> st = new ArrayList<>();
		// System.out.println(postexp);
		for (int i = 0; i < postexp.length();) {
			switch (postexp.charAt(i)) {
			case '+':
				Rational r1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				Rational r2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(r1.add(r2));
				break;
			case '-':
				r1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				r2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(r2.subtract(r1));
				break;
			case '*':
				r1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				r2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(r1.multiply(r2));
				break;
			case '/':
				r1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				r2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(r2.divide(r1));
				break;
			case '^':
				r1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				r2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(r2.pow((int) r1.getM_up()));
				break;
			default:
				long num = 0;
				while (i < postexp.length() && isNum(postexp, i)) {
					num = num * 10 + postexp.charAt(i) - '0';
					i++;
				}
				st.add(new Rational(num, 1));
				break;
			}
			i++;
			// for (Rational rational : st) {
			// System.out.print(rational);
			// System.out.print(" ");
			// }
			// System.out.println();
		}

		return st.get(st.size() - 1);
	}

	
	
	//产生除0的需要被T出
	public static ArrayList<ExpAndAns> generateExps(int num) {
		HashSet<MinPreFormat> hashSet = new HashSet<>();
		ArrayList<ExpAndAns> res = new ArrayList<>();
		for (int i = 0; i < num; i++) {
			String exp = generateNewExp();
			String postexp = trans(exp);
			Node root = createExpTree(postexp);
			MinPreFormat minPreFormat = minPre(root);
			if (hashSet.contains(minPreFormat)) {
				i--;
			} else {
				Rational ans = calc(postexp);
				if (ans.getM_down() == 0) {
					i--;
				} else {
					hashSet.add(minPreFormat);
					res.add(new ExpAndAns(exp, ans));
				}
			}
		}
		return res;
	}

	private static Node createExpTree(String postexp) {

		ArrayList<Node> st = new ArrayList<>();
		for (int i = 0; i < postexp.length();) {
			switch (postexp.charAt(i)) {
			case '+':
				Node nd1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				Node nd2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(new Node("+", nd2, nd1));
				break;
			case '-':
				nd1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				nd2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(new Node("-", nd2, nd1));
				break;
			case '*':
				nd1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				nd2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(new Node("*", nd2, nd1));
				break;
			case '/':
				nd1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				nd2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(new Node("/", nd2, nd1));
				break;
			case '^':
				nd1 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				nd2 = st.get(st.size() - 1);
				st.remove(st.size() - 1);
				st.add(new Node("^", nd2, nd1));
				break;
			default:
				String num = new String();
				while (i < postexp.length() && isNum(postexp, i)) {
					num += postexp.charAt(i);
					i++;
				}
				st.add(new Node(num, null, null));
				break;
			}
			i++;
		}

		return st.get(st.size() - 1);
	}


	private static MinPreFormat minPre(Node root) {
		if (root == null) {
			return null;
		}
		MinPreFormat LeftMinPre = minPre(root.getLeft());
		MinPreFormat RightMinPre = minPre(root.getRight());
		ArrayList<String> rootStrings = new ArrayList<>();
		rootStrings.add(root.getVal());
		MinPreFormat res = new MinPreFormat(rootStrings);
		MinPreFormatComparator minPreFormatComparator = new MinPreFormatComparator();
		if (LeftMinPre != null && RightMinPre != null) {
			if ((root.getVal().equals("+") || root.getVal().equals("*"))
					&& minPreFormatComparator.compare(LeftMinPre, RightMinPre) < 0) {
				res.getVal().addAll(RightMinPre.getVal());
				res.getVal().addAll(LeftMinPre.getVal());
			} else {
				res.getVal().addAll(LeftMinPre.getVal());
				res.getVal().addAll(RightMinPre.getVal());
			}
		} else {
			if (LeftMinPre != null) {
				res.getVal().addAll(LeftMinPre.getVal());
			}
			if (RightMinPre != null) {
				res.getVal().addAll(RightMinPre.getVal());
			}
		}
		return res;
	}
	
}
